#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>

#define Max_size 50

typedef struct //顺序串
{
    char str[Max_size];
    int length;
} SqlString;

void getNext(SqlString s, int next[]) //求next数组
{
    int i = 0, k = -1;
    next[0] = -1;
    while (i < s.length - 1) // next[i]的值时第i个字符前面的最长相等前后缀的的数
    {
        if (k == -1 || s.str[i] == s.str[k])
        {
            i++;
            k++;
            next[i] = k;
        }
        else
            k = next[k];
    }
}

int kmp(SqlString s, SqlString t) // kmp算法
{
    int next[Max_size], i = 0, j = 0;
    getNext(t, next);
    while (i < s.length && j < t.length)
    {
        if (j == -1 || s.str[i] == t.str[j])
        {
            i++;
            j++;
        }
        else
            j = next[j];
    }
    if (j >= t.length)
        return i - t.length;
    else
        return -1;
}

int BF(SqlString s, SqlString t) //暴力求解算法
{
    int i = 0, j = 0;
    while (i < s.length && j < t.length)
    {
        if (s.str[i] == t.str[j])
        {
            i++;
            j++;
        }
        else
        {
            i = i - j + 1;
            j = 0;
        }
    }
    if (j >= t.length)
        return i - t.length;
    else
        return -1;
}

void getNextval(SqlString t, int nextval[]) //改进后的求nextval数组方法
{
    int i = 0, j = -1;
    nextval[0] = -1;
    while (i < t.length - 1)
    {
        if (j == -1 || t.str[j] == t.str[i])
        {
            i++;
            j++;
            if (t.str[i] != t.str[j])
            {
                nextval[i] = j;
            }
            else
                nextval[i] = nextval[j];
        }
        else
            j = nextval[j];
    }
}

int kmpindex1(SqlString s, SqlString t) // 改进后的kmp算法
{
    int nextval[Max_size], i = 0, j = 0;
    getNextval(t, nextval);
    while (i < s.length && j < t.length)
    {
        if (j == -1 || s.str[i] == t.str[j])
        {
            i++;
            j++;
        }
        else
            j = nextval[j];
    }
    if (j >= t.length)
        return i - t.length;
    else
        return -1;
}

int main()
{
    SqlString s, t;
    strcpy(s.str, "abcabcdabcdeabcdefabcdefg");
    strcpy(t.str, "abcdeabcdefab");
    s.length = strlen(s.str);
    t.length = strlen(t.str);

    int pos = BF(s, t); //简单匹配算法
    // int pos = kmp(s, t);//kmp匹配算法
    // int pos = kmpindex1(s,t); //改进后的kmp算法
    if (pos != -1)
        printf("子串在主串中的首个位置(下标)是 %d\n", pos);
    else
        printf("主串中不存在该子串\n");

    return 0;
}
